package main

import "fmt"

/*
	给定一个三角形，找出自顶向下的最小路径和
	每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标和上一层结点下标相同或者等于上一层节点下标+1的两个结点。
	也就是说，如果正位于当前行的下标i，那么下一步可以移动到下一行的下标i或i+1
*/

func minimumTotal(triangle [][]int) int{
	// value[i,j] = min(value[i-1,j-1], [i,j-1])+value
	if len(triangle)>1 {
		for i := 1; i < len(triangle); i++ {
			for j := 0; j < len(triangle[i]); j++ {
				minValue := 0
				if j > 0 &&j!=len(triangle[i])-1&&triangle[i-1][j-1] < triangle[i-1][j]&&j!=len(triangle[i])-1{
					minValue = triangle[i-1][j-1]
				} else if j==len(triangle[i])-1 {
					minValue = triangle[i-1][j-1]
				} else {
					minValue = triangle[i-1][j]
				}
				triangle[i][j] += minValue
			}
		}
	}
	minimum := 99999
	fmt.Println(triangle)
	for k:=0;k<len(triangle[len(triangle)-1]);k++{
		if triangle[len(triangle)-1][k]<minimum{
			minimum = triangle[len(triangle)-1][k]
		}
	}
	return minimum
}

func main(){
	triangle := [][]int{
		{-10},
	}
	print(minimumTotal(triangle))
}
